package com.tencent;

import com.advanced.OddEvenList;

import java.util.List;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-30 15:02:33
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-30     张李鑫                     1.0         1.0 Version
 */
public class DetectCycle {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。
    //
    //为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    //如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
    //
    //说明：不允许修改给定的链表。


    public static ListNode detectCycle(ListNode head) {
        if (head == null && head.next == null && head.next.next== null) {
            return null;
        }
        ListNode p1 = head.next;
        ListNode p2 = head.next.next;
        while (p1 != null && p2 != null) {
            p1 = p1.next;
            p2 = p2.next == null ? null : p2.next.next;
            if (p2 == p1) {
                p2 = head;
                while (p2 != null && p1 != null) {
                    if (p2 == p1) {
                        return p1;
                    }
                    p2=p2.next;
                    p1=p1.next;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        //head = [3,2,0,-4], pos = 1
        ListNode listNode = new ListNode(3);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(0);
        ListNode listNode3 = new ListNode(-4);

        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode1;

        ListNode listNode4 = detectCycle(listNode);
        System.out.println(123123);

    }
}
